class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& rooti, int begin, int end) {
        if (begin > end)
            return nullptr;

        TreeNode* root = new TreeNode(preorder[rooti++]);


        int temp = begin;
        while (temp <= end)
        {
            if (preorder[rooti - 1] == inorder[temp])
                break;
            else
                temp++;
        }


        root->left = _buildTree(preorder, inorder, rooti, begin, temp - 1);
        root->right = _buildTree(preorder, inorder, rooti, temp + 1, end);


        return root;


    }


    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return _buildTree(preorder, inorder, i, 0, preorder.size() - 1);
    }
};
